표준 템플릿 라이브러리(Standard Template Library)컨터이너 및 알고리즘을 위한 기본 라이브러리
도입 예제컨테이너는 개체를 포함하는 클래스다.(vecotr, list 등)
각 클래스 템플릿은 요소의 타입을 통해 매개변수화된다.
std::vector<double> vec_d;
std::vector<int> vec_i;
double vec_sum=std::accumulate(begin(vec), end(vec), 0.0);
double lst_sum=std::accumluate(begin(lst), end(lst), 0.0);
begin(), end()는 반복자를 반환한다.
C++03에서는 해당 멤버 함수를 사용하여야 했지만,
C++11에서는 자유 함수 표기법을 도입해 이를 개선
반복자(Iterator)STL의 핵심적인 추상화는 반복자이다.
반복자는 일반화된 포인터이다.
반복자는 역참조를 하고 비교할 수 있으며 참조된 위치를 변경할 수도 있다.
반복자는 자료구조와 알고리즘의 구현을 분리하는 기본적인 방법이다.
STL의 모든 자료구조는 반복자를 제공하며, 모든 알고리즘은 반복자를 고려해 구현한다.
vector, deque, map, set 등의 자료구조는 copy, insert, replace, sort 등 알고리즘을 반복자를 고려해 구현
기존 절차지향 프로그래밍에서는 n개의 자료구조에 대하여 m개의 알고리즘을 구현하기 위해 m x n개의 구현이 필요
반복자를 이용하면, m+n개만 구현해주면 된다.
반복자의 종류컨테이너에서 제공하는 반복자의 종류에 따라 동작하는 알고리즘이 다름
접근 형태에 따른 구분
InputIterator: (단 한번만)참조된 항목을 읽는 반복자 컨셉
OutputIterator: (단 한번만)참조된 항목을 쓰는 반복자 컨셉
순회 형태에 따른 구분
ForwardIterator: 하나의 요소에서 다음 요소로 전달할 수 있는 반복자 컨셉
operator++를 제공
InputIterator를 개선한 반복자
BidirectionalIterator: 단계별 순방향 및 역방향 순회를 갖는 반복자 컨셉
operator++, operator—를 제공
ForwardIterator를 개선한 반복자
RandomAccessIterator: 임의의 양수 혹은 음수 오프셋을 더할 수 있는 반복자 컨셉
operator[]를 제공
BidirectionalIterator를 개선한 반복자
| 반복자 종류 |
사용 방식 |
읽기 |
접근 |
쓰기 |
증감 |
비교 |
| Input Iterator |
istream_iterator |
=*p |
-> |
|
++ |
== != |
| Output Iterator |
ostream_iterator |
*p= |
|
|
++ |
|
| front_inserter |
|
| back_inserter |
|
| inserter |
|
| Forward
Iterator |
=*p |
-> |
*p= |
++ |
== != |
| Bidirectional Iterator |
list |
=*p |
-> |
*p= |
++ -- |
== != |
| set & multiset |
| map&multimap |
| Randomaccess Iterator |
general pointer |
=*p |
->
[ ] |
*p= |
++ -- |
== != |
| vector |
+ - |
< > |
| deque |
+= -= |
<= >= |
반복자로 작업하기
using namespace std;
std::list<int> l={3, 5, 9, 7};
for (list<int>::iterator it=l.begin(); it != l.end(); ++it){
int i=*it;
cout<<i<<endl;
}
반복자는 일반적으로 쌍으로 생성해서 사용한다.
(해당 컨테이너 클래스에서 표준 메소드 begin(), end()를 사용해서 생성)
begin()는 첫 번째 요소를 가르키는 반복자를, end()는 마지막 요소의 다음을 가르키는 반복자를 반환
end()로 반환받은 반복자는 대부분 접근하려는 시도가 실패하기 때문에 비교에만 사용된다.
STL의 모든 알고리즘은 b=e가 될 때까지 b를 통해 참조된 값에서 동작하는 [b, e)으로 구현한다.
멤버함수 begin(), end()는 컨테이너의 불변성을 보존한다.
- 컨테이너 개체가 변경 불가능한 경우, 이 메서드는 변경 불가능한 컨테이너 항목을 참조하는 반복자 타입을 반환
- 상수 컨테이너의 경우, 메서드는 const 레퍼런스를 통해 컨테이너 항목에 접근하는 const_iterator를 반환
using namespace std;
std::list<int> l={3, 5, 9, 7};
for(auto it=begin(l), e=end(l); it!=e; ++it){
int i=*it;
std::cout<<i<<std::endl;
}
C++11 에서 도입된 begin(), end() 자유함수를 사용해 더 관용적인 표기법을 사용 가능하다.
begin(), end() 자유함수는 inline 함수로 바꾸더라도 성능에 영향을 주지 않는다.
e=end(l)로 선언해 주었기 때문에, 반복해서 end함수를 호출할 위험이 없음
(컴파일러에 따라서 반복해서 호출하지 않을 수도 있음)
const_iteratorbeing(), end()는 상수 리스트의 경우 const_iterator를 반환한다.
const std::list<int>& lr=l;
for(auto it=begin(lr), e=end(lr); it!=e; ++it){ }
for(auto it=begin(const_cast<const std::list<int>&>(l)), e=end(const_cast<const std::list<int>&>(l)); it!=e, ++it){ }
C++11에서는 상수 컨테이너 및 변경 가능한 컨테이너 모두에 대해 const_iterator를 반환하는
cbegin(), cend()를 도입했다.
C++14에서는 자유함수로 도입
for(auto it=cbegin(l); it!=cend(l); ++it){ }
범위 기반 for 문범위 기반 for 문은 begin-end 기반 탐색 패턴이 도입 계기가 된다.
std::list<int> l={3, 5, 9, 7};
for(auto i: l) std::cout<<i<<std::endl;
범위 기반 for문의 i는 컴테이너 전체를 순환하는 역참조된 (숨겨진)반복자이다.
내부적으로 begin 및 end 함수를 이용해서 for문을 구현
컨테이너 항목을 i로 복사하는 오버헤드를 피하기 위해 타입 추론된 레퍼런스로 사용할 수 있다.
for(auto& i: l) std::cout<<i<<std::endl;
레퍼런스 i는 l과 동일한 불변성을 가진다.
만일 l이 변경 가능한/상수 컨테이너(범위)라면, 레퍼런스 또한, 변경 가능하다
for(const auto& i: l) std::cout<<i<<std::endl;
동작<iterator> 라이브러리는 두 가지 기본 동작인
advance와 distance 함수를 제공한다.
advance
advance(it, n)은 반복자 it를 n번 증분한다.
it+n 동작을 수행하지만, it+n은 반복자 it을 변경하지 않으며 RandomAccessIterator일 때만 동작
하지만, advance 함수는 it+=n처럼 반복자 it을 변경하며, RandomAccessIterator가 아닌 반복자에도 동작
template <typename Iterator, typename Distance>
inline void advance_aux(Iterator& i, Distance n, input_iterator_tag){
assert(n>=0);
for(; n>0; --n) ++i;
}
template <typename Iterator, typename Distance>
inline void advance_aux(Iterator& i, Distance n, bidirectional_iter_tag){
if(n>=0) for(; n>0; --n) ++i;
else for(; n<0); ++n) --i;
}
template <typename Iterator, typename Distance>
inline void advance_aux(Iterator& i, Distance n, random_access_iterator_tag){
i+=n;
}
template<typename Iterator, typename Distance>
inline void advance(Iterator& i, Distance n){
advance(i, n, typename iterator_category<Iterator>::type());
}
advance 함수가 반복자 타입으로 인스턴스화되면, 반복자의 카테고리는 타입 특성(type trait)을 통해 결정된다.
태그 타입(Tag Type)는 advance_aux의 오버로드를 결정하는데 사용된다.
임의 접근 연산자의 경우 실행 시간이 상수이고 그 외는 선형
최신 컴파일러는 advance_aux의 각 오버로드에서 세 번째 인수를 사용하지 않을 경우,
태그 타입이 빈 클래스라는 것을 암묵적으로 인식한다.
(태그 타입 개체의 인수 전달 및 구성을 최적화한다.)
여분의 함수 레이어와 태그 디스패치는 런타임 오버로드를 발생시키지 않는다.
distance
distance함수는 advance의 인원화된 대응
int i=distance(it1, it2);
distance 함수는 두 반복자 사이의 거리
(첫 번째 반복자가 두 번째 반복자와 같은 위치에 있기 위해 얼마나 증가해야 하는지를 계산)
임의 접근 연산자의 경우 실행 시간이 상수이고 그 외는 선형